package doujian.match.algo;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 二部图匹配，dfs版匈牙利算法
 * 纯算法部分，使用时需格式化输入和输出
 * 算法输入为图的邻接矩阵，横轴为home,竖轴为student
 * 算法输出为包含了匹配信息的ArrayList
 * <p>
 * Created by majie on 17/4/14.
 */

public class Hungarian {
    int[][] graph;
    int match[];//记录匹配情况
    int state[];//记录是否访问过
    int n, m;
    int maxMatch = 0;


    public static class Match {
        public int home;
        public int stu;

        public Match(int x, int y) {
            this.home = x;
            this.stu = y;
        }
    }

    /**
     * 使用邻接矩阵初始化
     *
     * @param graph
     */
    public Hungarian(int[][] graph) {
        this.graph = graph;
        this.n = graph.length;
        this.m = graph[0].length;
        match = new int[n];
        Arrays.fill(match, -1);
        state = new int[n];
    }

    /**
     * 进行最大匹配
     * 暂时使用ArrayList<Match>作为结果
     *
     * @return
     */
    public ArrayList<Match> maxMatch() {
        maxMatch = 0;
        for (int i = 0; i < n; i++) {
            Arrays.fill(state, 0);
            maxMatch += find(i);
        }
        ArrayList<Match> list = new ArrayList<Match>();
        for (int i = 0; i < match.length; i++) {
            if (match[i] != -1) {
                list.add(new Match(i, match[i]));
            }
        }

        return list;
    }

    /**
     * dfs寻找增广路径
     *
     * @param x
     * @return
     */
    private int find(int x) {
        for (int i = 0; i < m; i++) {
            if (graph[x][i] == 1 && state[i] == 0) {
                state[i] = 1;
                if (match[i] == -1 || find(match[i]) > 0) {
                    match[i] = x;
                    return 1;
                }
            }
        }
        return 0;
    }

    /**
     * 测试用main函数
     *
     * @param args
     */
    public static void main(String args[]) {
        int[][] test1 = {{1, 1, 1, 0, 0},
                {0, 1, 1, 0, 0},
                {0, 0, 0, 1, 0},
                {0, 1, 0, 0, 0},
                {0, 0, 0, 1, 0}};
        System.out.print(new Hungarian(test1).maxMatch());

        int[][] test2 = {{0, 1, 0},
                {1, 1, 0},
                {0, 1, 0},
                {0, 0, 1}};
        System.out.print(new Hungarian(test2).maxMatch());

        int[][] test3 = {{0, 1, 0, 0},
                {1, 1, 0, 0},
                {0, 0, 1, 1}};
        System.out.print(new Hungarian(test3).maxMatch());
    }
}
